「GXOI/GZOI2019」旅行者

发表于 | 分类于 | | 浏览量： 次

随机算法多好啊。

传送门

洛谷P5304

BZOJ5506

题解

对于这题，一开始能比较容易地想到一个乱搞的做法：

将$k$个关键点随机分成两半，建立超级源点向其中一半的所有点建边权为$0$的边，再从另一半向超级汇点建边权为$0$的边。

然后用Dijkstra求出源点到汇点的最短路，取每次求解出最短路的最小值为答案。

这样一次求出最优解的概率为$\frac{1}{4}$。

但是如果我们重复以上操作20次，那么求出最优解的概率为$1-(\frac{3}{4})^{20}\approx99.7\%$。

这样AC的概率其实已近非常高了，如果能优化常数然后增大重复次数，那么AC的概率还可以进一步提高。

其实如果想到了上面乱搞的做法，离正解也很近了。

我们可以根据关键点编号在二进制中第$i$位上的数字来对这$k$个关键点进行分组，为$0$的分在一组，为$1$的分在另一组。然后按照上面的方式建图求最短路。

假设最优解中的起点为$u$，终点为$v$，那么它们编号在二进制中至少有一位不同，所以它们必定会在某一次分组中被分在了不同的组，从而求解出了答案。

时间复杂度$O(nlog^2n )$。

注意由于图是有向的，所以每枚举到二进制中的一位时应进行两次分组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=100005,maxm=500005;const LL inf=0x3F3F3F3F3F3F3F3FLL;
int T,n,m,k,V[maxn];LL ans,dist[maxn];
inline char nc()
{
	static const int S=131072;static char buf[S],*L,*R;
	return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;
}
inline int read()
{
	int ret=0,f=1;char ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}
	return ret*f;
}
struct Graph
{
	int tot,lnk[maxn],son[maxm],nxt[maxm],w[maxm];
	inline void Clear(){tot=0;memset(lnk,0,sizeof(lnk));}
	inline void add_e(int x,int y,int z){tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
}G1,G2;
struct Node
{
	int id;LL dis;
	bool operator < (const Node& b)const{return dis>b.dis;}
};
inline void Dijkstra()
{
	memset(dist,63,sizeof(dist));
	priority_queue<Node> que;
	que.push((Node){n+1,0});
	dist[n+1]=0;
	while(!que.empty())
	{
		Node QH=que.top();que.pop();
		if(QH.id==n+2&&QH.dis<ans) ans=QH.dis;
		if(QH.dis>dist[QH.id]) continue;
		dist[QH.id]=QH.dis;
		for(int i=G2.lnk[QH.id];i;i=G2.nxt[i])
			if(QH.dis+G2.w[i]<dist[G2.son[i]])
				que.push((Node){G2.son[i],QH.dis+G2.w[i]});
	}
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();m=read();k=read();G1.Clear();G2.Clear();ans=inf;
		for(int i=1;i<=m;i++)
		{
			int a=read(),b=read(),c=read();
			G1.add_e(a,b,c);G2.add_e(a,b,c);
		}
		for(int i=1;i<=k;i++) V[i]=read();
		for(int i=0;(1<<i)<=n;i++)
		{
			G2.tot=G1.tot;
			memcpy(G2.lnk,G1.lnk,(n+3)*sizeof(int));
			for(int j=1;j<=k;j++)
			{
				if(V[j]&(1<<i)) G2.add_e(n+1,V[j],0);
				else G2.add_e(V[j],n+2,0);
			}
			Dijkstra();
			G2.tot=G1.tot;
			memcpy(G2.lnk,G1.lnk,(n+3)*sizeof(int));
			for(int j=1;j<=k;j++)
			{
				if(V[j]&(1<<i)) G2.add_e(V[j],n+2,0);
				else G2.add_e(n+1,V[j],0);
			}
			Dijkstra();
		}
		printf("%lld\n",ans);
	}
	return 0;
}